原始题目:剑指 Offer 38. 字符串的排列 (opens new window)
解题思路:
对于长度为 的不重复字符串,它的排列方案有 种。
可以采取字符交换的方式,先固定第 位、再固定第 位、……、最后固定第 位。如下图:
以 "acb" 为例子,来讲述生成过程的思路。
- 初始时字符数组为 {'a', 'b', 'c'} ,且所有的交换都是和本身以及后面的元素交换。
- 固定第 位,第 位固定为 a(代码中就是 a 和 a 位置交换),剩下的可操作字符串就是 "bc"。
- 固定第 位,第 位可以固定为 b 或者 c (代码中就是 b 和 b 交换位置,或者 b 和 c 交换位置)
- 假设 b 和 c 交换位置,那么第二位固定为 c,剩下的可操作字符串就是 "b"。
- 固定第 位,第 位只剩下一个 b 可以选择,因此整个过程结束。此时字符数组的内容就是 {'a', 'c', 'b'} 。
**如果后面的元素有重复的话,就不需要交换了,因为会产生一个重复的结果。**因此碰到重复的元素,要跳过。
这个过程实际是一个深度优先搜索+剪枝法的结合
dfs函数
**传递参数:**当前固定位 。
**终止条件:**当 时,表示 已经时最后一个字符了,只有一种情况,因此将组合 转化成字符串加入 列表。
递推工作:
- 初始化一个集合 ,用来排除重复的字符串。
- 将第 位的字符与 的字符分别交换,然后进入下一层递归
- 剪枝:如果 在 中,代表这个字符已经交换过了,跳过这个字符。
- 交换字符:将 位置和 位置的字符进行交换
- 下一层递归:将当前位置 作为参数,传递给下一层递归。
- 还原字符:将 位置和 位置的字符再进行一次交换。
- 将 加入到 中,方便后面的剪枝。
代码:
List<String> ans = new ArrayList<>();
char[] chars;
public String[] permutation(String s) {
chars = s.toCharArray();
dfs(0);
return ans.toArray(new String[0]);
}
private void dfs(int x) {
if (x == chars.length) {
ans.add(new String(chars));
return;
}
HashSet<Character> set = new HashSet<>();
for (int i = x; i < chars.length; i++) {
if (set.contains(chars[i])) {
// 剪枝
continue;
}
swap(i, x);
dfs(x + 1);
swap(i, x);
set.add(chars[i]);
}
}
private void swap(int i, int j) {
char tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
复杂度分析
- 时间复杂度: 为字符串的长度,最坏情况下,所有字符都不相同,需要生成 个结果,每个结果都需要使用 的时间来拼接字符串。
- 空间复杂度: 为字符串的长度,整个过程累计递归栈空间为 ;每层递归中辅助集合存储的字符串数量最多为 ,及占用 的空间。